# -*- coding: UTF-8 -*-
# Python 快速排序算法
# @Author: Andevilin
# Email:100169328@qq.com
# @FileName: quick_sort.py  @Time: 2024/6/30 9:31  
"""
快速排序：
快速排序（Quick Sort）是一种常用的排序算法，其平均时间复杂度为 O(nlogn)。快速排序的主要思想是分治法，通过递归地将数组划分为较小和较大的两个子数组，然后递归地排序两个子数组。

以下是快速排序的实现步骤：

1. 选择一个基准元素（pivot）：可以选择第一个、中间元素或者最后一个元素作为基准。
2. 将数组划分为两个子数组：所有比基准元素小的元素放在基准元素的左边，所有比基准元素大的元素放在基准元素的右边。
3. 对两个子数组递归地应用快速排序算法。

以下是快速排序的 Python 实现：

```python
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

arr = [3,6,8,10,1,2,1]
print(quick_sort(arr))
```

在这个例子中，我们首先定义了一个名为 `quick_sort` 的函数，它接受一个数组作为参数。然后，我们检查数组的长度是否小于等于 1，如果是，则直接返回数组。否则，我们选择一个基准元素（pivot），将数组划分为两个子数组：所有比基准元素小的元素放在基准元素的左边，所有比基准元素大的元素放在基准元素的右边。最后，我们递归地应用快速排序算法对两个子数组进行排序，并将结果合并。
"""
import time

def calculae_runtime(func):
    def wrapper(*args, **kwargs):
        start_time = time.perf_counter()
        result = func(*args, **kwargs)
        end_time = time.perf_counter()
        runtime = end_time - start_time
        print(f"运行时间：{end_time - start_time}秒")
        return result,runtime
    return wrapper

# 定义快速排序函数
#@calculae_runtime
def quick_sort(arr):
    # 如果数组长度小于等于1，直接返回数组
    if len(arr) <= 1:
        return arr
    # 选择数组中间的元素作为基准值
    pivot = arr[len(arr) // 2]
    # 定义三个列表，分别存放比基准值小的元素、等于基准值的元素、大于基准值的元素
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    # 递归调用快速排序函数，对左、右两个列表进行排序，然后将结果合并
    return quick_sort(left) + middle + quick_sort(right)


# 主函数
@calculae_runtime
def main():
    # 定义一个数组
    arr = [3, 6, 8, 10, 1, 2, 1]
    # 调用快速排序函数，打印排序后的结果
    print(quick_sort(arr))


# 如果直接运行这个文件，则执行主函数
if __name__ == '__main__':
    main()
